{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Repeated String Match"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: repeatedStringMatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重复叠加字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串&nbsp;<code>a</code> 和 <code>b</code>，寻找重复叠加字符串 <code>a</code> 的最小次数，使得字符串 <code>b</code> 成为叠加后的字符串 <code>a</code> 的子串，如果不存在则返回 <code>-1</code>。</p>\n",
    "\n",
    "<p><strong>注意：</strong>字符串 <code>&quot;abc&quot;</code>&nbsp;重复叠加 0 次是 <code>&quot;&quot;</code>，重复叠加 1 次是&nbsp;<code>&quot;abc&quot;</code>，重复叠加 2 次是&nbsp;<code>&quot;abcabc&quot;</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>a = &quot;abcd&quot;, b = &quot;cdabcdab&quot;\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>a 重复叠加三遍后为 &quot;ab<strong>cdabcdab</strong>cd&quot;, 此时 b 是其子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>a = &quot;a&quot;, b = &quot;aa&quot;\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>a = &quot;a&quot;, b = &quot;a&quot;\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>a = &quot;abc&quot;, b = &quot;wxyz&quot;\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= a.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= b.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>a</code> 和 <code>b</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [repeated-string-match](https://leetcode.cn/problems/repeated-string-match/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [repeated-string-match](https://leetcode.cn/problems/repeated-string-match/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcd\"\\n\"cdabcdab\"', '\"a\"\\n\"aa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        ans=\"\"+a\n",
    "        i=1\n",
    "        if b==\"\":\n",
    "            return 0\n",
    "        if len(ans)>=len(b):\n",
    "            if b in ans:\n",
    "                return 1\n",
    "        while len(ans)<=len(b):\n",
    "            if b in ans:\n",
    "                return i\n",
    "            ans+=a\n",
    "            i+=1\n",
    "        if b in ans:\n",
    "            return i\n",
    "        elif b in ans+a:\n",
    "            return i+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_next(p: str) -> List[int]:\n",
    "    n = len(p)\n",
    "    arr = [0] * n\n",
    "    j = 0\n",
    "    for i in range(1, n):\n",
    "        while j > 0 and p[i] != p[j]:\n",
    "            j = arr[j - 1]\n",
    "        if p[i] == p[j]:\n",
    "            j += 1\n",
    "        arr[i] = j\n",
    "    return arr\n",
    "\n",
    "def str_cmp(arr: List[int], p: str, t: str) -> int:\n",
    "    n = len(t)\n",
    "    m = len(p)\n",
    "    j = 0\n",
    "    for i in range(n):\n",
    "        while j > 0 and t[i] != p[j]:\n",
    "            j = arr[j - 1]\n",
    "        if t[i] == p[j]:\n",
    "            j += 1\n",
    "        if j == m:\n",
    "            return i - m + 1\n",
    "    return -1\n",
    "\n",
    "M = 10 ** 9 + 7\n",
    "\n",
    "def get_hash(s: str, b: int=131, m=M) -> int:\n",
    "    last = 0\n",
    "    for ch in s:\n",
    "        last = last * b + ord(ch)\n",
    "    return last\n",
    "\n",
    "def str_hash(p: str, t: str) -> int:\n",
    "    b = 131\n",
    "    n, m = len(t), len(p)\n",
    "    pattern_hash = get_hash(p)\n",
    "\n",
    "    h = [0] * (n + 1)\n",
    "    bp = [0] * (n + 1)\n",
    "    bp[0] = 1\n",
    "    for i in range(n):\n",
    "        h[i + 1] = h[i] * b + ord(t[i])\n",
    "        bp[i + 1] = bp[i] * b\n",
    "    \n",
    "    for i in range(m - 1, n):\n",
    "        r = i + 1\n",
    "        l = r - m + 1\n",
    "        # target_hash = h[r] - h[l - 1] * bp[r - l + 1] if l - 1 > 0 else h[r]\n",
    "        target_hash = h[r] - h[l - 1] * bp[r - l + 1]\n",
    "        # print(f\": target: {target_hash}, pattern: {pattern_hash}\")\n",
    "        # print(f\": i: {i}, l: {l}, r: {r}, p: {p}, \")\n",
    "        if target_hash == pattern_hash:\n",
    "            return l - 1\n",
    "    return -1\n",
    "\n",
    "def new_str_hash(p: str, t: str) -> int:\n",
    "    b = 131\n",
    "    n, m = len(p), len(t)\n",
    "    s = p + t\n",
    "    size = len(s) \n",
    "    h = [0] * (size + 2)\n",
    "    bp = [0] * (size + 2)\n",
    "    bp[0] = 1\n",
    "    for i in range(size):\n",
    "        h[i + 1] = h[i] * b + ord(s[i])\n",
    "        bp[i + 1] = bp[i] * b\n",
    "    \n",
    "    p_r = size\n",
    "    p_l = size - m + 1\n",
    "    pattern_hash = h[p_r] - h[p_l - 1] * bp[p_r - p_l + 1]\n",
    "\n",
    "    for i in range(1, size - m + 1):\n",
    "        l = i\n",
    "        r = i + m - 1\n",
    "        target_hash = h[r] - h[l - 1] * bp[r - l + 1]\n",
    "        if target_hash == pattern_hash:\n",
    "            return l - 1\n",
    "    return -1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        if b == \"\":\n",
    "            return 0\n",
    "        arr = get_next(b)\n",
    "        # 下界： 大于等于b的长度, 上界：下界+1\n",
    "        new_str = \"\"\n",
    "        ans = 0\n",
    "        while len(new_str) < len(b):\n",
    "            ans += 1\n",
    "            new_str += a\n",
    "        new_str += a\n",
    "        m = str_cmp(arr, b, new_str)\n",
    "        # m = str_hash(b, new_str)\n",
    "        if m == -1:\n",
    "            return -1\n",
    "        return ans + 1 if m + len(b) > len(a) * ans else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        return l if(a*(l:=ceil(len(b)/len(a)))).find(b)!=-1 else l+1 if (a*(l+1)).find(b)!=-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        len_a = len(a)\n",
    "        len_b = len(b)\n",
    "        cnt = len_b // len_a + 4\n",
    "        for i in range(1, cnt):\n",
    "            str_temp = a *  i\n",
    "            if b in str_temp:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        count = 0\n",
    "        for i in range(80) if len(b) < len(a) * 80 else range(100000):\n",
    "            if b in a * i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        mn = len(b) // len(a)\n",
    "        for i in range(mn, mn+3):\n",
    "            if b in (a * i):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        r=math.ceil(len(b)/len(a))\n",
    "        for rr in range(r,r+3):\n",
    "            if b in a*rr:return rr\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "            a_set = set(a)\n",
    "            b_set = set(b)\n",
    "\n",
    "            if a_set & b_set != b_set: return -1\n",
    "\n",
    "            times = math.ceil(len(b) / len(a))\n",
    "            if b in a * times:\n",
    "                return times\n",
    "            elif b in a * (times + 1):\n",
    "                return times + 1\n",
    "            else:\n",
    "                return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "      ct = 1\n",
    "      c = a\n",
    "      if b == '':\n",
    "          return 0\n",
    "      if len(a) >= len(b) and b in a:\n",
    "          return 1\n",
    "      if b in 2 * a:\n",
    "        return 2\n",
    "      else:\n",
    "          while len(a) <= len(b)*2:\n",
    "              a = c * ct\n",
    "              if b in a:\n",
    "                  return ct\n",
    "              ct += 1\n",
    "      return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        i = 1\n",
    "        c = a\n",
    "        while len(c) <= 10**4:\n",
    "            c = a * i\n",
    "            if b in c:\n",
    "                return i\n",
    "            i += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        aa, c = '', 0\n",
    "        while len(aa) <= len(b)*2 or c < 2:\n",
    "            aa, c = aa + a, c + 1\n",
    "            if b in aa:\n",
    "                return c\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        count = 1\n",
    "        aa = a\n",
    "        for i in b:\n",
    "            if i not in a:\n",
    "                return -1\n",
    "        if len(a)>len(b):\n",
    "            if b in a:\n",
    "                return 1\n",
    "            if b in a+a:\n",
    "                return 2\n",
    "        while len(aa) <= len(b)*2:\n",
    "            if b in aa:\n",
    "                break\n",
    "            aa = aa+a\n",
    "            count += 1\n",
    "        if b in aa:\n",
    "            return count\n",
    "        else: return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "\n",
    "        for idx, char in enumerate(a):\n",
    "            if char != b[0]:\n",
    "                continue\n",
    "\n",
    "            repeat = 1\n",
    "            jdx = idx\n",
    "\n",
    "            for ch in b:\n",
    "                if jdx == len(a):\n",
    "                    jdx = 0\n",
    "                    repeat += 1\n",
    "\n",
    "                if a[jdx] != ch:\n",
    "                    break\n",
    "                \n",
    "                jdx += 1\n",
    "            else:\n",
    "                return repeat\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        time = ceil(len(b)/len(a))\n",
    "        if (a*time).find(b) != -1:\n",
    "            return time\n",
    "        elif (a*(time+1)).find(b) != -1:\n",
    "            return time+1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        if b == '':\n",
    "            return 0\n",
    "        if b in a:\n",
    "            return 1\n",
    "        if b in a*2:\n",
    "            return 2\n",
    "        c = b.split(a)\n",
    "        if a.endswith(c[0]) and a.startswith(c[-1]):\n",
    "            for i in c:\n",
    "                if i not in a:\n",
    "                    return -1\n",
    "            ans = len(c)\n",
    "            if c[0] != '' and c[-1] != '':\n",
    "                ans += 1\n",
    "            if c[0] == '' and c[-1] == '':\n",
    "                ans -= 1\n",
    "            return ans\n",
    "        return -1\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        time = len(b)//len(a)\n",
    "        if time > 0: cur = a*time\n",
    "        elif b in a:\n",
    "            return 1\n",
    "        else: \n",
    "            cur = a\n",
    "        if b in cur:\n",
    "            return time\n",
    "        cur = a*(time+1)\n",
    "        if b in cur:\n",
    "            return time+1\n",
    "        cur = a*(time+2)\n",
    "        if b in cur:\n",
    "            return time+2\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        #解决方式：贪心\n",
    "        '''\n",
    "        如果字符串A比字符串B长：\n",
    "        （1）字符串A本来就包含字符串B，这时A仅复制一遍就找到了，最大长度为len(A)；\n",
    "        （2）字符串A复制一遍包含字符B，这时A的重复次数为2，遍历控制范围是len(A)2；\n",
    "        （3）字符串A复制一遍不包含字符B，那么无论复制多少遍也不包含字符B，控制长度在len(A)2即可。\n",
    "        如果字符串A比字符串B短，我们将字符串A复制到刚好大于字符串B的长度，长度控制为不小于len(B)时跳出循环。\n",
    "        以上两种情况取最大值，求和即可：len(A)*2+len(B)。\n",
    "        '''\n",
    "        #给定一个循环次数初始值,给定一个叠加后的a\n",
    "\n",
    "        a_repeat, r = a, 1\n",
    "        while len(a_repeat) < 2 * len(a) + len(b):\n",
    "            if b in a_repeat:\n",
    "                return r\n",
    "            a_repeat, r = a_repeat + a, r + 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n, m  = len(a), len(b)\n",
    "        min_repeat = (m - 1) // n + 1\n",
    "\n",
    "        max_repeat = min_repeat + 1\n",
    "\n",
    "        print(min_repeat, max_repeat)\n",
    "        new_a = a * min_repeat\n",
    "\n",
    "        if new_a.find(b) != -1:\n",
    "            return min_repeat\n",
    "        \n",
    "        a = new_a + a \n",
    "\n",
    "        if a.find(b) != -1:\n",
    "            return max_repeat\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        res,len_a,len_b = 1,len(a),len(b)\n",
    "        i = t = b.find(a)\n",
    "        if i!=-1:\n",
    "            j = i+len_a\n",
    "            while j<len_b:\n",
    "                res+=1\n",
    "                if b[i:j] != a:\n",
    "                    return -1\n",
    "                i,j = j,j+len_a\n",
    "        tail,pre = b[:t],b[i:]\n",
    "        b = tail+pre\n",
    "        if res>1  and a.find(pre) != 0: return -1\n",
    "\n",
    "        s = a+a\n",
    "        # print(res,a,s,b,a.find(b),s.find(b))\n",
    "        if a.find(b) != -1: return res\n",
    "        if s.find(b) != -1: return res+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        # 特殊情况处理\n",
    "        if not a or not b:\n",
    "            return -1\n",
    "        if b in a:\n",
    "            return 1\n",
    "        \n",
    "        # 计算重复叠加的次数上限\n",
    "        max_repeats = math.ceil(len(b) / len(a))\n",
    "        \n",
    "        # 构造重复叠加后的字符串\n",
    "        repeated_a = a * max_repeats\n",
    "        \n",
    "        # 判断是否存在子串匹配\n",
    "        if b in repeated_a:\n",
    "            return max_repeats\n",
    "        \n",
    "        # 再叠加一次字符串 a，并判断是否存在子串匹配\n",
    "        repeated_a += a\n",
    "        if b in repeated_a:\n",
    "            return max_repeats + 1\n",
    "        \n",
    "        # 不存在匹配\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        \n",
    "        k = len(b)//len(a)\n",
    "        if b in a*k:\n",
    "            return k\n",
    "        elif b in a*(k+1):\n",
    "            return k+1\n",
    "        elif b in a *(k+2):\n",
    "            return k+2\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n, m = len(a), len(b)\n",
    "        cnt = math.ceil(m / n) + 1\n",
    "        s = \"\"\n",
    "        for i in range(cnt):\n",
    "            s += a\n",
    "            if b in s:\n",
    "                return i + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, A: str, B: str) -> int:\n",
    "        if B in A:\n",
    "            return 1\n",
    "        num = 1\n",
    "        a = A\n",
    "        while True:\n",
    "            num += 1\n",
    "            A += a\n",
    "            if B in A:\n",
    "                return num\n",
    "                break\n",
    "            if len(A)>len(B)+len(a):\n",
    "                return -1\n",
    "                break\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        # if any(x not in set(a) for x in set(b)):\n",
    "        #     return -1\n",
    "        s = ''\n",
    "        ans = 0\n",
    "        while len(s) < 2 * len(a) + len(b):\n",
    "            s += a\n",
    "            ans += 1\n",
    "            if b in s:\n",
    "                return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        return l if (a * (l:=ceil(len(b)/len(a)))).find(b) != -1 else l + 1 if (a * (l + 1)).find(b) != -1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        ans = 0\n",
    "        max = 2 * len(a) + len(b)\n",
    "        tmp = ''\n",
    "        while len(tmp) < max:\n",
    "            tmp += a\n",
    "            ans += 1\n",
    "            if b in tmp:\n",
    "                return ans\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        if set(b) - set(a): return -1\n",
    "        x = (len(b) - 1) // len(a) + 1\n",
    "        if b in a * x: return x\n",
    "        if b in a * (x + 1): return x + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        ans = 1\n",
    "        if b in a:\n",
    "            return ans\n",
    "        t = a\n",
    "        while len(t) <= 2 * len(a) + len(b):\n",
    "            ans += 1\n",
    "            t += a\n",
    "            if b in t:\n",
    "                return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        # 其实将a进行循环拼接的预处理更佳\n",
    "        # 本质还是匹配子串\n",
    "        if b == '':\n",
    "            return 0\n",
    "        n, m = len(a), len(b)\n",
    "        base,mod=147,10**9+777\n",
    "        ans = 1\n",
    "        \n",
    "        bh,mul=0,1\n",
    "        h=0\n",
    "        for i in range(m):\n",
    "            bh=(bh*base%mod+ord(b[i]))%mod\n",
    "            mul=(mul*base)%mod\n",
    "            h=((h*base%mod)+ord(a[i%n]))%mod\n",
    "        if h==bh:\n",
    "            return math.ceil(m/n)\n",
    "        i, j= 0, 0\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            h=((h*base%mod)+ord(a[(i+m-1)%n])-ord(a[i-1])*mul%mod)%mod\n",
    "            if h==bh:\n",
    "                return math.ceil((i+m)/n)\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def repeatedStringMatch(self, a, b):\n",
    "        if set(b) - set(a): return -1\n",
    "        x = (len(b) - 1) // len(a) + 1  # 刚好能整除的时候少一个\n",
    "        if b in a * x: return x\n",
    "        if b in a * (x + 1): return x + 1\n",
    "        return -1        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        #存在集合不一致，不匹配\n",
    "        if set(b) - set(a): return -1\n",
    "        x = 1\n",
    "        x = (len(b) - 1) // len(a) + 1\n",
    "        if b in a * x: return x\n",
    "        if b in a * (x + 1): return x + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def repeatedStringMatch(self, a, b):\n",
    "        if set(b) - set(a): return -1\n",
    "        x = (len(b) - 1) // len(a) + 1  # 刚好能整除的时候少一个\n",
    "        if b in a * x: return x\n",
    "        if b in a * (x + 1): return x + 1\n",
    "        return -1        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def repeatedStringMatch(self, a, b):\n",
    "        if set(b) - set(a): return -1\n",
    "        x = (len(b) - 1) // len(a) + 1\n",
    "        if b in a * x: return x\n",
    "        if b in a * (x + 1): return x + 1\n",
    "        return -1        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        res,len_a,len_b = 1,len(a),len(b)\n",
    "        i = t = b.find(a)\n",
    "        if i!=-1:\n",
    "            j = i+len_a\n",
    "            while j<len_b:\n",
    "                res+=1\n",
    "                if b[i:j] != a:\n",
    "                    return -1\n",
    "                i,j = j,j+len_a\n",
    "        b = b[:t]+b[i:]\n",
    "        if res>1 and a.find(b[t:]) != 0: return -1\n",
    "\n",
    "        if a.find(b) != -1: return res\n",
    "        if (a+a).find(b) != -1: return res+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        min_repeats = len(b) // len(a)\n",
    "        max_repeats = min_repeats + 3  # 加2是为了考虑边界情况\n",
    "\n",
    "        for repeat in range(min_repeats, max_repeats):\n",
    "            if b in a * repeat:\n",
    "                return repeat\n",
    "        return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        aS, bS = set(a), set(b)\n",
    "        if aS & bS != bS:\n",
    "            return -1\n",
    "\n",
    "        times = math.ceil(len(b) / len(a))\n",
    "        if b in a * times:\n",
    "            return times\n",
    "        elif b in a * (times + 1):\n",
    "            return times + 1\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        lenth=len(a)\n",
    "        if len(b)<lenth:\n",
    "            if b in a:\n",
    "                return 1\n",
    "            elif b in a*2:\n",
    "                return 2\n",
    "            else:\n",
    "                return -1\n",
    "        for i in range(lenth):\n",
    "            first=b[:i]\n",
    "            temp=b[i:]\n",
    "            left=len(temp)//lenth\n",
    "            second_num=len(temp)%lenth\n",
    "            if second_num!=0:\n",
    "                second=b[-second_num:]\n",
    "            else:\n",
    "                second=''\n",
    "            dd=left*a\n",
    "\n",
    "            #return first,temp,left,second,dd\n",
    "\n",
    "            if dd in temp:\n",
    "\n",
    "\n",
    "\n",
    "                if (first==a[-len(first):] or first=='') and second==a[:len(second)]:\n",
    "                    adjust=0\n",
    "                    if first!='':\n",
    "                        adjust+=1\n",
    "                    if second!='':\n",
    "                        adjust+=1\n",
    "                    return left+adjust\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        t = len(b)//len(a)\n",
    "        for i in range(4):\n",
    "            if b in (a * (t + i)):\n",
    "                return t + i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        min_num = ceil(len(b)/len(a))\n",
    "        target = a*min_num\n",
    "        \n",
    "        \n",
    "        for i in range(2):\n",
    "            print(target)\n",
    "            if b not in target:\n",
    "                target += a\n",
    "            else:\n",
    "                return min_num+i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        res,len_a,len_b = 1,len(a),len(b)\n",
    "        i = t = b.find(a)\n",
    "        if i!=-1:\n",
    "            j = i+len_a\n",
    "            while j<len_b:\n",
    "                res+=1\n",
    "                if b[i:j] != a:\n",
    "                    return -1\n",
    "                i,j = j,j+len_a\n",
    "        tail,pre = b[:t],b[i:]\n",
    "        b = tail+pre\n",
    "        print(tail,pre)\n",
    "        if res>1 and len(pre) and a.find(pre) != 0: return -1\n",
    "\n",
    "        s = a+a\n",
    "        # print(res,a,s,b,a.find(b),s.find(b))\n",
    "        if a.find(b) != -1: return res\n",
    "        if s.find(b) != -1: return res+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n = len(b) // len(a)\n",
    "        for i in range(n, n+3):\n",
    "            c = a * i\n",
    "            if c.find(b) != -1:\n",
    "                return i\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        i = 1\n",
    "        tmp_a = a\n",
    "        while len(tmp_a) <= 2*len(a) + len(b):\n",
    "            tmp_a = a * i\n",
    "            if b in tmp_a:\n",
    "                return i\n",
    "            i += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def strstr(self, haystack: str, needle: str) -> int:\n",
    "        n, m = len(haystack), len(needle)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "\n",
    "        k1 = 10 ** 9 + 7\n",
    "        k2 = 1337\n",
    "        mod1 = randrange(k1) + k1\n",
    "        mod2 = randrange(k2) + k2\n",
    "\n",
    "        hash_needle = 0\n",
    "        for c in needle:\n",
    "            hash_needle = (hash_needle * mod2 + ord(c)) % mod1\n",
    "        hash_haystack = 0\n",
    "        for i in range(m - 1):\n",
    "            hash_haystack = (hash_haystack * mod2 + ord(haystack[i % n])) % mod1\n",
    "        extra = pow(mod2, m - 1, mod1)\n",
    "        for i in range(m - 1, n + m - 1):\n",
    "            hash_haystack = (hash_haystack * mod2 + ord(haystack[i % n])) % mod1\n",
    "            if hash_haystack == hash_needle:\n",
    "                return i - m + 1\n",
    "            hash_haystack = (hash_haystack - extra * ord(haystack[(i - m + 1) % n])) % mod1\n",
    "            hash_haystack = (hash_haystack + mod1) % mod1\n",
    "        return -1\n",
    "\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n, m = len(a), len(b)\n",
    "        index = self.strstr(a, b)\n",
    "        if index == -1:\n",
    "            return -1\n",
    "        if n - index >= m:\n",
    "            return 1\n",
    "        return (m + index - n - 1) // n + 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        m, n = len(a), len(b)\n",
    "        pi = [0] * n\n",
    "\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and b[i] != b[j]:\n",
    "                j = pi[j-1]\n",
    "            if b[i] == b[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        index = -1\n",
    "        while i - j < m:\n",
    "            while j > 0 and a[i%m] != b[j]:\n",
    "                j = pi[j-1]\n",
    "            if b[j] == a[i%m]:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                index = i\n",
    "                break\n",
    "            i += 1\n",
    "        \n",
    "        if index == -1: return -1\n",
    "        else:\n",
    "            return (i + 1) // m if (i + 1) % m == 0 else (i + 1) // m + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        m,n=len(a),len(b)\n",
    "\n",
    "        if set(list(a))!=set(list(b)) and m<=n:\n",
    "            return -1\n",
    "\n",
    "        for i in range((n-1)//m+1,(n-1)//m+3):\n",
    "            s= a*i\n",
    "            j=0\n",
    "            \n",
    "            while j < m*i-n+1:\n",
    "                \n",
    "                k=0\n",
    "\n",
    "                while  k<n and j<m*i and s[j]==b[k]:\n",
    "                    k+=1\n",
    "                    j+=1\n",
    "\n",
    "                if k==n:\n",
    "                    return i\n",
    "                    \n",
    "                else:\n",
    "                    j=j-k+1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        def get_next(s:str) -> List[int]:\n",
    "            nt = [-1, 0]\n",
    "            k = 0\n",
    "            for i in range(2, len(s)):\n",
    "                while k > 0 and s[k + 1] != s[i]:\n",
    "                    k = nt[k]\n",
    "                \n",
    "                if s[k + 1] == s[i]:\n",
    "                    k += 1\n",
    "                \n",
    "                nt.append(k)\n",
    "            return nt\n",
    "\n",
    "        an, bn = len(a), len(b)\n",
    "        ans = 1\n",
    "        comp = a\n",
    "        nt = get_next(b)\n",
    "        while ans * an < bn:\n",
    "            comp += a\n",
    "            ans += 1\n",
    "\n",
    "        def kmp(s1:str):\n",
    "            k = -1\n",
    "            for i in range(len(s1)):\n",
    "                while k > -1 and b[k + 1] != s1[i]:\n",
    "                    k = nt[k]\n",
    "                \n",
    "                if b[k+1] == s1[i]:\n",
    "                    k += 1\n",
    "                \n",
    "                if k+1 == bn:\n",
    "                    return True\n",
    "            \n",
    "            return False\n",
    "            \n",
    "        if kmp(comp):\n",
    "            return ans\n",
    "        \n",
    "        if kmp(comp + a):\n",
    "            return ans + 1\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefix_function(self,s:str):\n",
    "        n = len(s)\n",
    "        pi = [0] * n\n",
    "        for i in range(1,n):\n",
    "            j = pi[i-1]\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = pi[j-1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "        return pi\n",
    "    def kmp(self,s:str,b:str) -> int:\n",
    "        pi = self.prefix_function(b)\n",
    "        j = 0\n",
    "        for i in range(0,len(s)):\n",
    "            while j > 0 and s[i] != b[j]:\n",
    "                j = pi[j-1]\n",
    "            if(s[i] == b[j]): j += 1\n",
    "            if(j == len(b)): return i-len(b)+1\n",
    "        return -1\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        low = 1\n",
    "        high = max(100,int(2 * len(b) / len(a)))\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            aa = \"\"\n",
    "            for i in range(0,int(mid)):\n",
    "                aa += a\n",
    "            if self.kmp(aa,b) != -1: high = mid\n",
    "            else : low = mid + 1\n",
    "        if high == max(100,int(2 * len(b) / len(a))) : return -1\n",
    "        return int(low)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        match_list = list(map(lambda p: p.span(), re.finditer(a, b)))\n",
    "        if match_list:\n",
    "            first_match = max(0, match_list[0][0])\n",
    "            last_match = min(len(b), match_list[-1][-1])\n",
    "            if len(match_list) >= 2:\n",
    "                for i in range(len(match_list) - 1):\n",
    "                    if match_list[i][1] != match_list[i+1][0]:\n",
    "                        return -1\n",
    "            res = len(match_list)\n",
    "            if first_match > 0:\n",
    "                m = re.search(b[first_match - 1::-1], a[::-1])\n",
    "                if m and m.span()[0] == 0:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            if last_match < len(b):\n",
    "                m = re.search(b[last_match:], a)\n",
    "                if m and m.span()[0] == 0:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            return res\n",
    "        else:\n",
    "            m = re.search(b, a + a)\n",
    "            if m is None:\n",
    "                return -1\n",
    "            elif m.span()[1] <= len(a):\n",
    "                return 1\n",
    "            else:\n",
    "                return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        # # 思路1、根据字符串长度关系分析出 重复次数的最小取值和最大取值\n",
    "        # result = 1\n",
    "        # # 重复次数的最小取值：保证长度上能够覆盖b字符串\n",
    "        # if len(b) % len(a) == 0:\n",
    "        #     result = len(b) // len(a)\n",
    "        # else:\n",
    "        #     result = len(b) // len(a) + 1\n",
    "        # # 重复次数的最大取值：最小取值+1；再多的重复次数没有必要了，匹配情况会跟此时的最大取值一样\n",
    "        # # 能匹配上时，更多的重复串是冗余的；无法匹配上时，更多的重复串也匹配不上\n",
    "        # result += 1\n",
    "        # newA = a * result\n",
    "        # nextArr = [0] * len(b)\n",
    "        # self.gexNext(nextArr, b)\n",
    "        # j = 0  # 标记匹配串中 最长匹配前缀位置+1\n",
    "        # for i in range(len(newA)):  # i负责遍历原串\n",
    "        #     # 没匹配上：需要持续回退&判断是否匹配上，如果一直匹配不上，j会回到起始位置0\n",
    "        #     while j > 0 and newA[i] != b[j]:\n",
    "        #         j = nextArr[j - 1]\n",
    "        #     if newA[i] == b[j]:\n",
    "        #         j += 1\n",
    "        #     if j == len(b):  # 匹配上了：讨论匹配位置是否超出result-1次重复的最大值索引\n",
    "        #         if i <= (result - 1) * len(a) - 1:\n",
    "        #             return result - 1\n",
    "        #         else:\n",
    "        #             return result\n",
    "        # return -1\n",
    "\n",
    "        # 思路2、根据题意满足时，匹配上的开始位置是否在第一个重复原串中判断：如果不在，说明再多重复也不会匹配上；如果在，讨论重复次数\n",
    "        index = self.strStr(a, b)\n",
    "        if index == -1:\n",
    "            return -1\n",
    "        elif index + len(b) - 1 <= len(a) - 1:\n",
    "            return 1\n",
    "        else:\n",
    "            if (len(b) + index) % len(a) == 0:  # 想不通官方答案怎么能把这两种情况统一起来的\n",
    "                return (len(b) + index) // len(a)\n",
    "            else:\n",
    "                return (len(b) + index) // len(a) + 1\n",
    "\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        nextArr = [0] * len(needle)\n",
    "        self.getNext(nextArr, needle)  # 获取next数组\n",
    "        # 执行字符串匹配的过程\n",
    "        i, j = 0, 0\n",
    "        while i - j < len(haystack):  # i-j就是当前匹配发生的起始位置，<n表示发生在第一个a中；\n",
    "            # 一旦匹配过程的起点不在第一个a中时，循环结束\n",
    "            while j > 0 and haystack[i % len(haystack)] != needle[j]:  # 当前字符不匹配：找j的下个比较位置\n",
    "                j = nextArr[j - 1]\n",
    "            if haystack[i % len(haystack)] == needle[j]:  # 当前字符匹配：看下一个字符\n",
    "                j += 1\n",
    "            if j == len(needle):  # 匹配成功\n",
    "                return i - len(needle) + 1\n",
    "            i += 1\n",
    "        return -1\n",
    "\n",
    "    def getNext(self, nextArr: List[int], b: str):\n",
    "        # i：字符串、next数组的遍历位置，也是当前字符的后缀末尾\n",
    "        # j：最长相等前缀末尾位置+1，即 最长相等的前后缀长度\n",
    "        j = 0\n",
    "        for i in range(1, len(b)):  # 遍历索引从1开始\n",
    "            # 没匹配上：持续回退，直到匹配上或回到起始位置\n",
    "            while j > 0 and b[i] != b[j]:\n",
    "                j = nextArr[j - 1]\n",
    "            # 匹配上\n",
    "            if b[i] == b[j]:\n",
    "                j += 1\n",
    "            nextArr[i] = j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n = len(a)\n",
    "        m = len(b)\n",
    "        #N = 10001\n",
    "        N = 10010\n",
    "        ne = [0] * (N + 1)\n",
    "        b = ' ' + b\n",
    "\n",
    "        i, j = 2, 0\n",
    "        #while j < m:\n",
    "        while i <= m:\n",
    "            while j and b[i] != b[j + 1]:\n",
    "                j = ne[j]\n",
    "            if b[i] == b[j + 1]:\n",
    "                j += 1\n",
    "            ne[i] = j\n",
    "            i += 1\n",
    "        \n",
    "        i = j = 0\n",
    "        while i - j < n:\n",
    "            while j and b[j + 1] != a[i % n]:\n",
    "                j = ne[j]\n",
    "            if  a[i % n] == b[j + 1]:\n",
    "                j += 1\n",
    "            i += 1\n",
    "            if j == m:\n",
    "                break\n",
    "        \n",
    "        if j == m: \n",
    "            return i // n if i % n == 0 else i // n + 1\n",
    "        else:\n",
    "            #-1\n",
    "            return -1\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "        for i in range(len(b)+1):\n",
    "            string = a * i\n",
    "            if b in string:\n",
    "                return i\n",
    "            else:\n",
    "                continue\n",
    "        return -1\n",
    "就是会超时啦\n",
    "别人正确的写法\n",
    "        shang = len(b)//len(a) #  “shang” 是 “商” 的意思\n",
    "        z = shang * a \n",
    "        x = (shang + 1) * a\n",
    "        c = (shang + 2) * a\n",
    "        if b in z:\n",
    "            return shang\n",
    "        elif b in x:\n",
    "            return shang + 1\n",
    "        elif b in c:\n",
    "            return shang + 2\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "作者：Saber酱\n",
    "链接：https://leetcode.cn/problems/repeated-string-match/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        if a.find(b) != -1:\n",
    "            return 1\n",
    "        import re\n",
    "        p = re.compile(f'(?:{a})+')\n",
    "        m = p.search(b)\n",
    "        if not m:\n",
    "            u = a + a\n",
    "            if u.find(b) != -1:\n",
    "                return 2\n",
    "            u = u + a\n",
    "            if u.find(b) != -1:\n",
    "                return 3\n",
    "            return -1\n",
    "        x = b[:m.start()]\n",
    "        y = b[m.end():]\n",
    "        if not a.endswith(x) or not a.startswith(y):\n",
    "            return -1\n",
    "        return (m.end() - m.start()) // len(a) + int(x != '') + int(y != '')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        # 本质还是匹配子串\n",
    "        if b == '':\n",
    "            return 0\n",
    "        n, m = len(a), len(b)\n",
    "        next = [0]*m\n",
    "        next[0] = -1\n",
    "        j = 0\n",
    "        for i in range(1, m-1):\n",
    "            # kmp[i] = kmp[i-1]+1 if b[i] == b[kmp[i-1]] else 0\n",
    "            while j > 0 and b[i] != b[j]:\n",
    "                j = next[j]\n",
    "            if b[i] == b[j]:\n",
    "                j += 1\n",
    "            next[i+1] = j\n",
    "        # for i in range(1, m):\n",
    "        #     if b[i] == b[next[i]]:\n",
    "        #         next[i] = next[next[i]]\n",
    "        ans = 1\n",
    "        i, j, k = 0, 0, 0\n",
    "        # i,j=0,0\n",
    "        # while k < n and j < m and ans*n<=m:\n",
    "        while j < m and (ans-1)*n+i-j<n:\n",
    "            while j >= 0 and a[i] != b[j]:\n",
    "                j = next[j]\n",
    "            # if a[i] != b[j]:\n",
    "            #     k = i+1\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "            if i >= n and j < m:\n",
    "                ans += 1\n",
    "                i %= n\n",
    "        if j == m:\n",
    "            return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        if not a or not b:\n",
    "            return -1\n",
    "        pi = [0] * len(b)\n",
    "        j = 0\n",
    "        for i in range(1, len(b)):\n",
    "            while j > 0 and b[i] != b[j]:\n",
    "                j = pi[j - 1]\n",
    "            if b[i] == b[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "\n",
    "        ii = 0\n",
    "        j = 0\n",
    "        for ii in range(len(b) + 2 * len(a)):\n",
    "            i = ii % len(a)\n",
    "            while (j > 0) and a[i] != b[j]:\n",
    "                j = pi[j - 1]\n",
    "            if a[i] == b[j]:\n",
    "                j += 1\n",
    "            if j == len(b):\n",
    "                break\n",
    "        ii += 1\n",
    "        if j != len(b):\n",
    "            return -1\n",
    "        else:\n",
    "            if ii % len(a) == 0:\n",
    "                return int(ii / len(a))\n",
    "            else:\n",
    "                return int(ii / len(a)) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class KMP:\r\n",
    "    def __init__(self,pattern:str) -> None:\r\n",
    "        L=len(pattern)\r\n",
    "        next=[0]*L\r\n",
    "        k=0\r\n",
    "        for i in range(1,L):\r\n",
    "            while k>0 and pattern[i]!=pattern[k]:\r\n",
    "                k=next[k-1]\r\n",
    "            if pattern[i]==pattern[k]:\r\n",
    "                k+=1\r\n",
    "            next[i]=k\r\n",
    "        self.next=next\r\n",
    "        self.pattern=pattern\r\n",
    "\r\n",
    "    def find(self,s:str):\r\n",
    "        L=len(s)\r\n",
    "        N=len(self.pattern)\r\n",
    "        i,j=0,0\r\n",
    "        # start=i\r\n",
    "        while i<L+j:\r\n",
    "            while j>0 and self.pattern[j]!=s[i%L]:\r\n",
    "                j=self.next[j-1]\r\n",
    "            # if j==0:\r\n",
    "            #     start=i\r\n",
    "            if self.pattern[j]==s[i%L]:\r\n",
    "                i+=1\r\n",
    "                j+=1\r\n",
    "                if j==N:\r\n",
    "                    return i-j\r\n",
    "            else:\r\n",
    "                i+=1\r\n",
    "        return -1\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\r\n",
    "        # La=len(a)\r\n",
    "        # Lb=len(b)\r\n",
    "        # if Lb>La:\r\n",
    "        #     base=(Lb-1)//La+1\r\n",
    "        #     a*=base\r\n",
    "\r\n",
    "        # idx=(2*a).find(b)\r\n",
    "        # if idx<0:\r\n",
    "        #     return -1\r\n",
    "        # return (idx+Lb-1)//La + 1\r\n",
    "        kmp=KMP(b)\r\n",
    "        idx=kmp.find(a)\r\n",
    "        if idx<0:\r\n",
    "            return -1\r\n",
    "        return (idx+len(b)-1)//len(a)+1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        m, n = len(a), len(b)\n",
    "        \n",
    "        kmp_nxt = [-1] * n \n",
    "        for i in range(1, n):\n",
    "            pre = kmp_nxt[i-1]\n",
    "            while pre >= 0 and b[pre] != b[i-1]:\n",
    "                pre = kmp_nxt[pre]\n",
    "            kmp_nxt[i] = pre + 1\n",
    "        \n",
    "        j = 0\n",
    "        for i in range(m + n - 1):\n",
    "            while j >= 0 and a[i%m] != b[j]:\n",
    "                j = kmp_nxt[j] \n",
    "            j += 1\n",
    "            if j == n:\n",
    "                return i // m + 1\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        # 本质还是匹配子串\n",
    "        if b == '':\n",
    "            return 0\n",
    "        n, m = len(a), len(b)\n",
    "        next = [0]*m\n",
    "        next[0] = -1\n",
    "        j = 0\n",
    "        for i in range(1, m-1):\n",
    "            # kmp[i] = kmp[i-1]+1 if b[i] == b[kmp[i-1]] else 0\n",
    "            while j > 0 and b[i] != b[j]:\n",
    "                j = next[j]\n",
    "            if b[i] == b[j]:\n",
    "                j += 1\n",
    "            next[i+1] = j\n",
    "        # for i in range(1, m):\n",
    "        #     if b[i] == b[next[i]]:\n",
    "        #         next[i] = next[next[i]]\n",
    "        ans = 1\n",
    "        i, j, k = 0, 0, 0\n",
    "        # i,j=0,0\n",
    "        # while k < n and j < m and ans*n<=m:\n",
    "        while j < m and (ans-1)*n+i-j<n:\n",
    "            while j >= 0 and a[i] != b[j]:\n",
    "                j = next[j]\n",
    "            # if a[i] != b[j]:\n",
    "            #     k = i+1\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "            if i >= n and j < m:\n",
    "                ans += 1\n",
    "                i %= n\n",
    "        if j == m:\n",
    "            return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 本题有一个关键的条件，如果没有在a的第一个周期就匹配上，那就不会匹配上了\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        def kmp(a, b):\n",
    "            left, m, n = 0, len(b), len(a)\n",
    "            next = [0] * m\n",
    "            for right in range(1, m):\n",
    "                while left > 0 and b[left] != b[right]:\n",
    "                    left = next[left - 1]\n",
    "                if b[left] == b[right]:\n",
    "                    left += 1\n",
    "                next[right] = left\n",
    "\n",
    "            i, j = 0, 0\n",
    "            while i - j < n:\n",
    "                while j > 0 and a[i % n] != b[j]:\n",
    "                    j = next[j - 1]\n",
    "                if a[i % n] == b[j]:\n",
    "                    j += 1\n",
    "                if j == m:\n",
    "                    return i - m + 1\n",
    "                i += 1\n",
    "            return -1\n",
    "\n",
    "        if len(b) == 0:\n",
    "            return 0\n",
    "        n, m = len(a), len(b)\n",
    "        index = kmp(a, b)\n",
    "        print(index)\n",
    "        if index == -1:\n",
    "            return index\n",
    "        if n - index >= m:\n",
    "            return 1\n",
    "        return (m + index - n - 1) // n + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        m, n = len(a), len(b)\n",
    "        j = 0\n",
    "        pi = [0] * n\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and b[i] != b[j]:\n",
    "                j = pi[j-1]\n",
    "            if b[i] == b[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        index = -1\n",
    "        while i - j < m:\n",
    "            while j > 0 and a[i%m] != b[j]:\n",
    "                j = pi[j-1]\n",
    "            if a[i%m] == b[j]:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                index = i\n",
    "                break\n",
    "            i += 1\n",
    "        if index == -1: return -1\n",
    "        elif (index + 1) % m == 0: return (index + 1) // m\n",
    "        else: return (index + 1) // m + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strstr(self, haystack: str, needle: str) -> int:\n",
    "        n, m = len(haystack), len(needle)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "\n",
    "        pi = [0] * m\n",
    "        j = 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and needle[i] != needle[j]:\n",
    "                j = pi[j - 1]\n",
    "            if needle[i] == needle[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while i - j < n:\n",
    "            while j > 0 and haystack[i % n] != needle[j]:\n",
    "                j = pi[j - 1]\n",
    "            if haystack[i % n] == needle[j]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                return i - m + 1\n",
    "            i += 1\n",
    "        return -1\n",
    "\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n, m = len(a), len(b)\n",
    "        index = self.strstr(a, b)\n",
    "        if index == -1:\n",
    "            return -1\n",
    "        if n - index >= m:\n",
    "            return 1\n",
    "        return (m + index - n - 1) // n + 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def kmp(self, sub: str, mai: str) -> bool:\n",
    "        next_ls = [-1] * len(sub)\n",
    "        m = 1\n",
    "        s = 0\n",
    "        if len(sub) >= 2:\n",
    "            next_ls[1] = 0 \n",
    "        while m < len(sub) - 1:\n",
    "            if sub[m] == sub[s] or s == -1:\n",
    "                m += 1\n",
    "                s += 1\n",
    "                next_ls[m] = s \n",
    "            else:\n",
    "                s = next_ls[s]\n",
    "        i = j = 0\n",
    "        while i < len(sub) and j < len(mai):\n",
    "            if sub[i] == mai[j] or i == -1:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i = next_ls[i]\n",
    "        if i == len(sub):\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "        \n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n_a, n_b = len(a), len(b)\n",
    "        min_num = math.ceil(n_b / n_a)\n",
    "        max_num = min_num + 1\n",
    "        for i in range(min_num, max_num + 1):\n",
    "            s = a * i\n",
    "            if self.kmp(b, s):\n",
    "                return i \n",
    "            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strstr(self, haystack: str, needle: str) -> int:\n",
    "        n, m = len(haystack), len(needle)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "\n",
    "        pi = [0] * m\n",
    "        j = 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and needle[i] != needle[j]:\n",
    "                j = pi[j - 1]\n",
    "            if needle[i] == needle[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while i - j < n:\n",
    "            while j > 0 and haystack[i % n] != needle[j]:\n",
    "                j = pi[j - 1]\n",
    "            if haystack[i % n] == needle[j]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                return i - m + 1\n",
    "            i += 1\n",
    "        return -1\n",
    "\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n, m = len(a), len(b)\n",
    "        index = self.strstr(a, b)\n",
    "        if index == -1:\n",
    "            return -1\n",
    "        if n - index >= m:\n",
    "            return 1\n",
    "        return (m + index - n - 1) // n + 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        s = ''\n",
    "        c = 0\n",
    "        while len(s) < len(b):\n",
    "            s += a\n",
    "            c += 1\n",
    "        s += a\n",
    "        idx = self.kmp(s, b)\n",
    "        #print(f'idx:{idx},s:{s},b:{b}')\n",
    "        if idx == -1:\n",
    "            return -1\n",
    "        end = idx + len(b) - 1\n",
    "        return c if end < len(a) * c else c + 1\n",
    "\n",
    "    def kmp(self,s: str, p: str) -> int:\n",
    "        n, m = len(s), len(p)\n",
    "        nxt = [0] * m\n",
    "        j = 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and p[i] != p[j]:\n",
    "                j = nxt[j - 1]\n",
    "            if p[i] == p[j]:\n",
    "                j += 1\n",
    "            nxt[i] = j\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j > 0 and s[i] != p[j]:\n",
    "                j = nxt[j - 1]\n",
    "            if s[i] == p[j]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                return i - m + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm\n",
    "    def kmp(self, next: List[int], pattern: str) -> None:\n",
    "        patternSize = len(pattern)\n",
    "\n",
    "        j = 0\n",
    "        for i in range(1, patternSize):\n",
    "            while (j > 0) and (pattern[i] != pattern[j]):\n",
    "                j = next[j-1]\n",
    "\n",
    "            if pattern[i] == pattern[j]:\n",
    "                j += 1\n",
    "\n",
    "            next[i] = j\n",
    "\n",
    "    def strstr(self, haystack: str, needle: str) -> int:\n",
    "        retVal = -1\n",
    "\n",
    "        needleSize = len(needle)\n",
    "        if needleSize == 0:\n",
    "            retVal = 0\n",
    "            return retVal\n",
    "        next = [0] * needleSize\n",
    "        self.kmp(next, needle)\n",
    "\n",
    "        haystackSize = len(haystack)\n",
    "        haystackIdx = 0\n",
    "        needleIdx = 0\n",
    "        while haystackIdx - needleIdx < haystackSize:\n",
    "            while (needleIdx > 0) and (haystack[haystackIdx % haystackSize] != needle[needleIdx]):\n",
    "                needleIdx = next[needleIdx - 1]\n",
    "\n",
    "            if haystack[haystackIdx % haystackSize] == needle[needleIdx]:\n",
    "                needleIdx += 1\n",
    "\n",
    "            if needleIdx == needleSize:\n",
    "                retVal = haystackIdx - needleSize + 1\n",
    "                break\n",
    "\n",
    "            haystackIdx += 1\n",
    "\n",
    "        return retVal\n",
    "\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        retVal = -1\n",
    "\n",
    "        aSize = len(a)\n",
    "        bSize = len(b)\n",
    "        index = self.strstr(a, b)\n",
    "        if index == -1:\n",
    "            retVal = -1\n",
    "        elif aSize - index >= bSize:\n",
    "            retVal = 1\n",
    "        else:\n",
    "            retVal = (bSize + index - aSize - 1) // aSize + 2\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strstr(self, haystack: str, needle: str) -> int:\n",
    "        n, m = len(haystack), len(needle)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "\n",
    "        pi = [0] * m\n",
    "        j = 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and needle[i] != needle[j]:\n",
    "                j = pi[j - 1]\n",
    "            if needle[i] == needle[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while i - j < n:\n",
    "            while j > 0 and haystack[i % n] != needle[j]:\n",
    "                j = pi[j - 1]\n",
    "            if haystack[i % n] == needle[j]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                return i - m + 1\n",
    "            i += 1\n",
    "        return -1\n",
    "\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n, m = len(a), len(b)\n",
    "        index = self.strstr(a, b)\n",
    "        if index == -1:\n",
    "            return -1\n",
    "        if n - index >= m:\n",
    "            return 1\n",
    "        return (m + index - n - 1) // n + 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "\n",
    "        res, n, m, l, j, k = 0, len(b), len(a), 0, 0, []\n",
    "        next = [0]*m     \n",
    "        \n",
    "        if m>=n and b in a:\n",
    "            return 1\n",
    "        if b in (a+a)[1:-1]:\n",
    "            return 2\n",
    "                \n",
    "        for r in range(1, m):\n",
    "            while l > 0 and a[l] != a[r]:\n",
    "                l = next[l - 1]\n",
    "            if a[l] == a[r]:\n",
    "                l += 1\n",
    "            next[r] = l\n",
    "\n",
    "        for i in range(n):\n",
    "            while j > 0 and b[i] != a[j]:\n",
    "                j = next[j - 1]\n",
    "            if b[i] == a[j]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                k.append(i - j + 1) \n",
    "                j = 0\n",
    "\n",
    "        nk = len(k)\n",
    "        if not(nk) or (nk > 1 and k[1]-k[0]!=m):\n",
    "            return -1\n",
    "\n",
    "        res += nk\n",
    "        if k[0]:\n",
    "            if b[k[0]-1]==a[-1]:\n",
    "                res += 1\n",
    "            else:\n",
    "                return -1\n",
    "        if k[-1]+m<n:\n",
    "            for i in range(min(m,n-k[-1]-m)):\n",
    "                if b[k[-1]+m+i]!=a[i]:\n",
    "                    return -1\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        n, m = len(a), len(b)\n",
    "\n",
    "        def kmp(haystack, needle):\n",
    "            n, m = len(haystack), len(needle)\n",
    "            if m == 0: return 0\n",
    "            pi = [0] * m\n",
    "            j = 0\n",
    "            for i in range(1, m):\n",
    "                while j > 0 and needle[i] != needle[j]:\n",
    "                    j = pi[j - 1]\n",
    "                if needle[i] == needle[j]:\n",
    "                    j += 1\n",
    "                pi[i] = j\n",
    "\n",
    "            i, j = 0, 0\n",
    "            while i - j < n:\n",
    "                while j > 0 and haystack[i % n] != needle[j]:\n",
    "                    j = pi[j - 1]\n",
    "                if haystack[i % n] == needle[j]:\n",
    "                    j += 1\n",
    "                if j == m:\n",
    "                    return i - m + 1\n",
    "                i += 1\n",
    "            return -1\n",
    "\n",
    "        idx = kmp(a, b)\n",
    "        if idx == -1:\n",
    "            return -1\n",
    "        if n - idx >= m:\n",
    "            return 1\n",
    "        return (m + idx - n - 1) // n + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        if len(b) == 0:\n",
    "            return 0\n",
    "        left, m, n = 0, len(b), len(a)\n",
    "        next = [0] * m\n",
    "        for right in range(1, m):\n",
    "            while left > 0 and b[left] != b[right]:\n",
    "                left = next[left - 1]\n",
    "            if b[left] == b[right]:\n",
    "                left += 1\n",
    "            next[right] = left\n",
    "        i, j = 0, 0\n",
    "        max_len = (len(b) // len(a) + 2) * len(a)\n",
    "        while j < m:\n",
    "            while j > 0 and a[i % n] != b[j]:\n",
    "                j = next[j - 1]\n",
    "            if a[i % n] == b[j]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                if (i + 1) % n == 0:\n",
    "                    return (i + 1) // n\n",
    "                else:\n",
    "                    return (i + 1) // n + 1\n",
    "            if i + 1 > max_len:\n",
    "                return -1\n",
    "            i += 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "\n",
    "        res, n, m, l, j, k = 0, len(b), len(a), 0, 0, []\n",
    "        next = [0]*m     \n",
    "        \n",
    "        if m>=n and b in a:\n",
    "            return 1\n",
    "        if b in (a+a)[1:-1]:\n",
    "            return 2\n",
    "                \n",
    "        for r in range(1, m):\n",
    "            while l > 0 and a[l] != a[r]:\n",
    "                l = next[l - 1]\n",
    "            if a[l] == a[r]:\n",
    "                l += 1\n",
    "            next[r] = l\n",
    "\n",
    "        for i in range(n):\n",
    "            while j > 0 and b[i] != a[j]:\n",
    "                j = next[j - 1]\n",
    "            if b[i] == a[j]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                k.append(i - j + 1) \n",
    "                j = 0\n",
    "\n",
    "        print(k)\n",
    "        nk = len(k)\n",
    "        if not(nk) or (nk > 1 and k[1]-k[0]!=m):\n",
    "            return -1\n",
    "\n",
    "        res += nk\n",
    "        if k[0]:\n",
    "            if b[k[0]-1]==a[-1]:\n",
    "                res += 1\n",
    "            else:\n",
    "                return -1\n",
    "        if k[-1]+m<n:\n",
    "            for i in range(min(m,n-k[-1]-m)):\n",
    "                if b[k[-1]+m+i]!=a[i]:\n",
    "                    return -1\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kmp(self, s, p):\n",
    "        m = len(p)\n",
    "        n = len(s)\n",
    "\n",
    "        s = \" \" + s\n",
    "        p = \" \" + p\n",
    "        ne = [0] * len(p)\n",
    "        ne[0] = -1\n",
    "\n",
    "        j = 0\n",
    "        for i in range(2, m + 1):\n",
    "            while j and p[i] != p[j + 1]:\n",
    "                j = ne[j]\n",
    "            if p[i] == p[j + 1]:\n",
    "                j += 1\n",
    "            ne[i] = j\n",
    "\n",
    "        j = 0\n",
    "        for i in range(1, n + 1):\n",
    "            while j and s[i] != p[j + 1]:\n",
    "                j = ne[j]\n",
    "            if s[i] == p[j + 1]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                return i - m  # start index\n",
    "\n",
    "        return -1\n",
    "\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        mi = int(len(b) / len(a))\n",
    "        if len(b) > mi * len(a):\n",
    "            mi += 1\n",
    "        strA = (mi + 1) * a\n",
    "\n",
    "        idx = self.kmp(strA, b)\n",
    "        if idx == -1:\n",
    "            return -1\n",
    "        return mi if idx + len(b) <= len(a) * mi else mi + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # KMP 匹配算法，T 为文本串，p 为模式串\n",
    "    def kmp(self, T: str, p: str) -> int:\n",
    "        n, m = len(T), len(p)\n",
    "\n",
    "        next = self.generateNext(p)\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while i - j < n:\n",
    "            while j > 0 and T[i % n] != p[j]:\n",
    "                j = next[j - 1]\n",
    "            if T[i % n] == p[j]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                return i - m + 1\n",
    "            i += 1\n",
    "        return -1\n",
    "\n",
    "    def generateNext(self, p: str):\n",
    "        m = len(p)\n",
    "        next = [0 for _ in range(m)]\n",
    "\n",
    "        left = 0\n",
    "        for right in range(1, m):\n",
    "            while left > 0 and p[left] != p[right]:\n",
    "                left = next[left - 1]\n",
    "            if p[left] == p[right]:\n",
    "                left += 1\n",
    "            next[right] = left\n",
    "\n",
    "        return next\n",
    "\n",
    "    def repeatedStringMatch(self, a: str, b: str) -> int:\n",
    "        len_a = len(a)\n",
    "        len_b = len(b)\n",
    "        index = self.kmp(a, b)\n",
    "        if index == -1:\n",
    "            return -1\n",
    "        if len_a - index >= len_b:\n",
    "            return 1\n",
    "        return (index + len(b) - 1) // len(a) + 1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
